#include <iostream>

// Define the fixpoint of a functor
//
template <template <typename> class F>
struct Fix : F< Fix<F> >
{};

// Define the 'Nat' algebra

template <typename T>
struct NatF
{
  struct Zero final : NatF
  {
    void scrut(void) throw (Zero*) override { throw this; }
    Zero(void) {} // static?
  private:
    Zero(const Zero&) = delete;
  };

  struct Succ final : NatF
  {
    NatF* payload;
    Succ(NatF* payload) : payload(payload) {}
    void scrut(void) throw (Succ*) override { throw this; }
  private:
    Succ(const Succ&) = delete;
  };

  operator T& (void); // do not inline here
  void operator ! (void)
  {
    // only works when T == Fix<NatF>
    throw static_cast<T*>(this);
  }
  virtual void scrut(void) __attribute__((noreturn)) = 0;
private:
  typedef T Fix; // for certain specializations
};

template <>
inline NatF< Fix<NatF> >::operator Fix& (void)
{
  return *static_cast<Fix*>(this);
}

typedef Fix<NatF> Nat;
typedef Nat::Zero Z;
typedef Nat::Succ S;

Z z;
S sz(&z);
S ssz(&sz);

Nat& add(Nat& m, Nat& n) throw ()
try {
  m.scrut();
 }
 catch(Z*) {
   return n;
 }
 catch(S* s) {
   return add(*s->payload, *new S(&n));
 }

Nat& mul(Nat& m, Nat& n) throw ()
try {
  m.scrut();
 }
 catch(Z* z) {
   return *z;
 }
 catch(S* s) {
   return add(n, mul(*s->payload, n));
 }

Nat& fak(Nat& n) throw ()
  try {
    n.scrut();
  }
  catch (Z* z) {
    return *new S(z);
  }
  catch (S* s) {
    return mul(*s, fak(*s->payload));
  }

void extract(Nat& n, unsigned& into)
 try {
   n.scrut();
 }
 catch (Z*)
   { return; }
 catch (S* s)
   {
     into++;
     extract(*s->payload, into);
   }

int main(void)
{
  try {
    !fak(add(ssz, mul(ssz, ssz)));
  }
  catch (Nat* n)
    {
      unsigned val(0);
      extract(*n, val);
      std::cout << "fak valued: " << val << std::endl;
    }

  try {
    fak(ssz);
  }
  catch (Nat* n)
    {
      unsigned val(0);
      extract(*n, val);
      std::cout << "fak valued: " << val << std::endl;
    }

  try {
    ssz.scrut();
  }
  catch (Z*)
  {
    std::cout << "zero!" << std::endl;
  }
  catch (S* s)
  {
    unsigned val(0);
    extract(*s, val);

    std::cout << "succ: payload " << s->payload << " valued: " << val << std::endl;
  }
}
